class SNode:
    """单链表节点"""

    def __init__(self, item=None):
        self.data = item
        self.next = None


class TSNode:
    """二叉树搜索节点"""

    def __init__(self, key=None, val=None, left=None, right=None, parent=None):
        self.key = key
        self.payload = val
        self.left_child: TSNode = left
        self.right_child: TSNode = right
        self.parent: TSNode = parent
        self.balance_factor = 0  # 叶子节点的平衡因子均为0

    def has_left_child(self):
        return self.left_child

    def has_right_child(self):
        return self.right_child

    def is_left_child(self):
        return self.parent and self.parent.left_child == self

    def is_right_child(self):
        return self.parent and self.parent.right_child == self

    def is_root(self):
        return not self.parent

    def is_leaf(self):
        return not (self.left_child or self.right_child)

    def has_any_child(self):
        return self.left_child or self.right_child

    def has_both_child(self):
        return self.left_child and self.right_child

    def replace_node_data(self, key, val, lc, rc):
        self.key = key
        self.payload = val
        self.left_child = lc
        self.right_child = rc
        if self.has_left_child():
            self.left_child.parent = self

        if self.has_right_child():
            self.right_child.parent = self

    def __iter__(self):
        if self:
            if self.has_left_child():
                for elem in self.left_child:
                    yield elem

            yield self.key

            if self.has_right_child():
                for elem in self.right_child:
                    yield elem

    def find_successor(self):
        succ = None
        if self.has_right_child():
            succ = self.right_child.find_min()
        # >> -----------------------
        # 这段代码在有双子节点寻找后的情况下不会被执行
        else:
            if self.parent:
                if self.is_left_child():
                    succ = self.parent
                else:
                    self.parent.right_child = None
                    succ = self.parent.find_successor()
                    self.parent.right_child = self
        # << -----------------------
        return succ

    def find_min(self):
        ret = self
        while ret.has_left_child():
            ret = ret.left_child
        return ret

    def splice_out(self):
        if self.is_leaf():
            if self.is_left_child():
                self.parent.left_child = None
            else:
                self.parent.right_child = None
        elif self.has_any_child():
            if self.has_left_child():
                # >> ----------------------------------
                # 这段代码在有双子节点寻找后的情况下不会被执行
                if self.is_left_child():
                    self.parent.left_child = self.left_child
                else:
                    self.parent.right_child = self.left_child
                self.left_child.parent = self.parent
                # << ----------------------------------
            else:
                if self.is_left_child():
                    self.parent.left_child = self.right_child
                else:
                    self.parent.right_child = self.right_child
                self.right_child.parent = self.parent
